#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: longest_palindrome_central_diffusion.py 
@version:
@time: 2023/12/24

相比于动态规划算法，中心扩展算法节约了存储空间，并降低了一定的时间复杂度。

所谓中心扩散算法，就是遍历原始字符串中的每个字符，依次判断以每个字符为中心的回文子串。

在向两边扩展的过程中，如果已经出现不是回文串的情况，那么就无须再扩展，因为一个回文子串其中心扩展开来的子串必定也会是回文串。

i:
minstart:
maxl:
l:
r:
"""


def longest_palindrome(s):
    if len(s) <= 1: return s
    i = minstart = 0
    maxl = 1
    while i < len(s):
        # 每轮遍历之前，先对当前最长回文子串的长度
        # 与以当前字符为中心可能得到的最长回文子串长度进行比较。
        """
        x x x x x x x x x
                    i  len(s)
        len(s) - i < maxl / 2
        """
        if len(s) - i < maxl / 2:
            break
        l = r = i
        """
        第二个需要注意的问题是在每个中心位置先向右扩展判断字符是否与中心字符相同，
        如果相同，则右指针向后移动。
        """
        while r < len(s) - 1 and s[r] == s[r + 1]:
            r += 1
        """
        在每轮遍历过程中，判断左指针和右指针指向的字符是否相同，
        如果相同，则继续向两侧扩展，如果不同，则停止扩展
        """
        while r < len(s) - 1 and l > 0 and s[l - 1] == s[r + 1]:
            r, l = r + 1, l - 1
        """
        每轮遍历过程中，要将以当前字符为中心点
        的最长回文子串和当前最长回文子串
        长度进行比较，然后更新
        """
        if r - l + 1 >= maxl:
            minstart, maxl = l, r - l + 1
        # 当前中心位置向后移动1
        i += 1
    return s[minstart:minstart + maxl]


print(longest_palindrome('abcdcba'))
